package main

import (
	"fmt"
)

/**
执行用时：0 ms, 在所有 Go 提交中击败了100.00%的用户
内存消耗：2.7 MB, 在所有 Go 提交中击败了84.49%的用户
 */
var ans [][]int
var path []int

func combinationSum(cs []int, target int) [][]int {

	ans = [][]int{}
	path = []int{}
	dfs(cs, target, 0)
	return ans
}

func dfs(cs []int, target int, u int) {

	if target == 0 {
		// 注意：要使用下面两行对全局变量进行拷贝
		t := make([]int, len(path))
		copy(t, path)

		ans = append(ans, t)
		return
	}
	if u == len(cs) { return }

	for i := 0; cs[u] * i <= target; i++ {
		dfs(cs, target - cs[u] * i, u + 1)
		path = append(path, cs[u])
	}

	for i := 0; cs[u] * i <= target; i++ {
		path = path[:len(path) - 1]
	}
}

func main() {

	cs := []int{2, 3, 5}
	fmt.Println(combinationSum(cs, 8))
}
